package 力扣._763_划分字母区间;

import java.util.LinkedList;
import java.util.List;

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new LinkedList<>();
        int[] last_c = new int[26];
        for (int i = 0; i < 26; i++) {
            last_c[i] = s.lastIndexOf('a' + i);
        }
        int begin = 0, last = 0;    // 当前区间的起始和结束下标
        while (last < s.length()) {
            for (int i = begin; i <= last; i++) {
                // 更新当前的区间的结束位置
                last = Math.max(last, last_c[s.charAt(i) - 'a']);
            }
            list.add(last - begin + 1);
            begin = last + 1;
            last = begin;
        }
        return list;
    }
}